package Lecture9;


import java.util.Arrays;

public class mergeExer {

	public static void main(String[] args) 
	{
		int[] array = {4,65,50,22,9,8,18,5,68,46,7,7,1};
		//int[] array = { 3, 537, 24, 500, 436,355,3,248,6,449,2,326,322,1,5};

		array = sortArray(array);
		System.out.println(Arrays.toString(array));
	}
	
	
	public static int[] sortArray(int[] array)
	{
		if (array.length > 1 )
		{
			int indElementsA1 = array.length/2;
			int indElementsA2 = array.length - indElementsA1;
			
			int[] arr1 = new int[indElementsA1];
			int[] arr2 = new int[indElementsA2];
			
			for( int i = 0 ; i < arr1.length; i++)
			{
				arr1[i] = array[i];
			}
			
			for( int i = arr1.length; i < array.length; i++)
			{
				arr2[i - indElementsA1] = array[i];
			}
			
			arr1 = sortArray(arr1);
			arr2 = sortArray(arr2);
					
			//System.out.println(Arrays.toString(arr1));
			//System.out.println(Arrays.toString(arr2));
		
			int i = 0, j = 0, k = 0;
			
			while( arr1.length != j && arr2.length != k)
			{
				if (arr1[j] < arr2[k])
				{
					array[i] = arr1[j];
					i++;
					j++;

				}
				else
				{
					array[i] = arr2[k];
					i++;
					k++;

							
				}
			}	
			//System.out.println(Arrays.toString(array));
			//System.out.println(Arrays.toString(arr1));
			//System.out.println(Arrays.toString(arr2));
				
				while(arr1.length != j)
				{
					array[i] = arr1[j];
					i++; 
					j++;
				}
				while (arr2.length != k)
				{
					array[i] = arr2[k];
					i++; 
					k++;
				}
				
		
		}
		
		
		
		
		return array;
	}

}
